import java.util.Arrays;

/**
 * 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
 * <p>
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
 * <p>
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：k = 2, prices = [2,4,1]
 * 输出：2
 * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
 * 示例 2：
 * <p>
 * 输入：k = 2, prices = [3,2,6,5,0,3]
 * 输出：7
 * 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
 * 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= k <= 100
 * 0 <= prices.length <= 1000
 * 0 <= prices[i] <= 1000
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(maxProfit(2, new int[]{4, 1, 2}));
        System.out.println(maxProfit(2, new int[]{2, 4, 1}));
        System.out.println(maxProfit(2, new int[]{3, 2, 6, 5, 0, 3}));
        System.out.println(maxProfit(1, new int[]{6, 1, 6, 4, 3, 0, 2}));
    }

    private static int[][] dp;
    private static int[][][] remark;

    /**
     * dp表存储i-j的最大利润
     * 这样子二分下去，切k-1下，求最值
     * 备忘录表remark存的是k次的情况下，i-j的最大利润
     * 备忘录表remark太大了，内存会爆
     *
     * @param prices
     * @return
     */
    public static int maxProfit(int k, int[] prices) {
        if (prices.length <= 1 || k < 1) {
            return 0;
        }
        k = Math.min(k, prices.length / 2 + 1);
        dp = new int[prices.length][prices.length];
        remark = new int[k][prices.length][prices.length];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < prices.length; j++) {
                Arrays.fill(remark[i][j], -1);
            }
        }
        for (int end = 1; end < prices.length; end++) {
            for (int start = end, tmp = 0, max = 0; start >= 0; start--) {
                if (prices[start] > max) {
                    max = prices[start];
                } else {
                    tmp = Math.max(tmp, max - prices[start]);
                }
                dp[start][end] = tmp;
            }
        }
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            res = Math.max(res, loop(1, 0, i) + loop(k - 1, i + 1, prices.length - 1));
        }
        return res;
    }

    /**
     * @param k
     * @param x
     * @param y
     * @return
     */
    private static int loop(int k, int x, int y) {
        if (y - x < 1 || k == 0) {
            return 0;
        }
        if (k == 1) {
            return dp[x][y];
        }
        if (remark[k][x][y] != -1) {
            return remark[k][x][y];
        }
        int res = 0;
        for (int i = x + 1; i <= y; i++) {
            res = Math.max(res, loop(1, x, i) + loop(k - 1, i + 1, y));
        }
        remark[k][x][y] = res;
        return res;
    }


}